﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace TSP
{
    class TSPSolverDivideNConquer : ITSPSolver
    {
        private DistanceGrid distanceGrid;
        public List<City> solveProblem(City[] input)
        {
            //initialize the index for each city
            for (int i = 0; i < input.Length; i++)
            {
                input[i].Index = (uint)i;
            }
            distanceGrid = new DistanceGrid(input);
            Stopwatch timer = new Stopwatch();
            timer.Start();
            Route result = divideNConquer(input.ToList());
            timer.Stop();
            Program.MainForm.tbElapsedTime.Text = timer.Elapsed.ToString();
            return result.ToList();
        }

        /// <summary>
        /// Takes the list of cities and using divide and conquer, returns a good route
        /// </summary>
        /// <param name="input">The list of cities for which we are finding a route</param>
        /// <returns>a good route</returns>
        private Route divideNConquer(List<City> input)
        {
            if (input.Count < 4)
            {
                return new Route(input.ToArray());
            }
            else
            {
                // Divide
                double maxX, minX, minY, maxY;
                // find the four quadrants
                findMinMaxValues(input, out minX, out maxX, out minY, out maxY);
                List<City> quadrant1 = new List<City>();
                List<City> quadrant2 = new List<City>();
                List<City> quadrant3 = new List<City>();
                List<City> quadrant4 = new List<City>();
                double midX = (minX + maxX) / 2;
                double midY = (minY + maxY) / 2;
                // place the points in their quadrants
                for (int i = 0; i < input.Count; ++i)
                {
                    City currentCity = input[i];
                    if (currentCity.X <= midX && currentCity.Y <= midY)
                        quadrant1.Add(currentCity);
                    else if (currentCity.X > midX && currentCity.Y < midY)
                        quadrant2.Add(currentCity);
                    else if (currentCity.X < midX && currentCity.Y > midY)
                        quadrant3.Add(currentCity);
                    else
                        quadrant4.Add(currentCity);
                }
                // divide the resulting quadrants further
                Route route1 = divideNConquer(quadrant1);
                Route route2 = divideNConquer(quadrant2);
                Route route3 = divideNConquer(quadrant3);
                Route route4 = divideNConquer(quadrant4);
                // Merge routes
                route1 = mergeRoutes(route1, route2);
                route2 = mergeRoutes(route3, route4);
                return mergeRoutes(route1, route2);
            }
        }

        //properly supports modulo of negative numbers
        private int mod(int x, int m)
        {
            int r = x % m;
            return r < 0 ? r + m : r;
        }

        private Route mergeRoutes(Route route1, Route route2)
        {
            // NOTE: one or both of the routes might be empty (have no cities)
            int oneLen = route1.Count;
            int twoLen = route2.Count;
            if (oneLen == 0)
            {
                return route2;
            }
            if (twoLen == 0)
            {
                return route1;
            }

            Tuple<double, int> tempBest = new Tuple<double, int>(0, 0);
            bool bsfSet = false;
            double bsf = Double.PositiveInfinity;
            int besti = 0, bestj = 0;

            //find the best merge
            //for i = 0 to route1.size
            for (int i = 0; i < oneLen; i++)
            {
                //for j = 0 to route2.size
                for (int j = 0; j < twoLen; j++)
                {
                    //tempBest = getBestMergePair(i, j, route1, route2)
                    tempBest = getBestMergePair(i, j, route1, route2);
                    //if !bsfSet
                    if (!bsfSet)
                    {
                        bsfSet = true;
                        bsf = tempBest.Item1;
                        continue;
                    }
                    //if tempBest.Item1 < bsf
                    if (tempBest.Item1 < bsf)
                    {
                        besti = i;
                        bestj = j;
                        bsf = tempBest.Item1;
                    }
                }
            }

            List<City> result = new List<City>();

            //create the merged route
            int newi, newj;
            //switch tempBest.Item2
            switch (tempBest.Item2)
            {
                case 0:
                    //start at b[j]
                    newj = bestj;
                    //go backwards and loop around until b[j+1]
                    do
                    {
                        result.Add(route2[newj]);
                        newj = mod(newj - 1, twoLen);
                    } while (newj != bestj);
                    //start at a[i+1]
                    newi = (besti + 1) % oneLen;
                    //go forwards and loop around until a[i]
                    do
                    {
                        result.Add(route1[newi]);
                        newi = (newi + 1) % oneLen;
                    } while (newi != (besti + 1) % oneLen);
                    break;

                case 1:
                    //start at b[j+1]
                    newj = (bestj + 1) % twoLen;
                    //go forwards and loop around until b[j]
                    do
                    {
                        result.Add(route2[newj]);
                        newj = (newj + 1) % twoLen;
                    } while (newj != (bestj + 1) % twoLen);
                    //start at a[i]
                    newi = besti;
                    //go backwards and loop around until a[i+1]
                    do
                    {
                        result.Add(route1[newi]);
                        newi = mod(newi - 1, oneLen);
                    } while (newi != besti);
                    break;

                case 2:
                    //start at b[j+1]
                    newj = (bestj + 1) % twoLen;
                    //go forwards and loop around until b[j]
                    do
                    {
                        result.Add(route2[newj]);
                        newj = (newj + 1) % twoLen;
                    } while (newj != (bestj + 1) % twoLen);
                    //start at a[i+1]
                    newi = (besti + 1) % oneLen;
                    //go forwards and loop around until a[i]
                    do
                    {
                        result.Add(route1[newi]);
                        newi = (newi + 1) % oneLen;
                    } while (newi != (besti + 1) % oneLen);
                    break;

                case 3:
                    //start at b[j]
                    newj = bestj;
                    //go backwards and loop around until b[j+1]
                    do
                    {
                        result.Add(route2[newj]);
                        newj = mod(newj - 1, twoLen);
                    } while (newj != bestj);
                    //start at a[i]
                    newi = besti;
                    //go backwards and loop around until a[i+1]
                    do
                    {
                        result.Add(route1[newi]);
                        newi = mod(newi - 1, oneLen);
                    } while (newi != besti);
                    break;
                //route1 and route2 each have one city
                case 4:
                    //route goes from a[0] to b[0] then back
                    result.Add(route1[0]);
                    result.Add(route2[0]);
                    break;
                //route1 has only one city
                case 5:
                    result.Add(route1[0]);
                    newj = (bestj + 1) % twoLen;
                    do
                    {
                        result.Add(route2[newj]);
                        newj = (newj + 1) % twoLen;
                    } while (newj != (bestj + 1) % twoLen);
                    break;
                //route2 has only one city
                case 6:
                    result.Add(route2[0]);
                    newi = (besti + 1) % oneLen;
                    do
                    {
                        result.Add(route1[newi]);
                        newi = (newi + 1) % oneLen;
                    } while (newi != (besti + 1) % oneLen);
                    break;
            }

            return new Route(result.ToArray());
            //throw new NotImplementedException();
        }

        //return which resulting path is shortest
        private Tuple<double, int> getBestMergePair(int i, int j, Route a, Route b)
        {
            //first number: path length
            //second number:
            //0 if a[i] to b[j] + b[j+1] to a[i+1]
            //1 if b[j] to a[i] + a[i+1] to b[j+1]
            //2 if a[i] to b[j+1] + b[j] to a[i+1]
            //3 if b[j+1] to a[i] + a[i+1] to b[j]
            double tempDist, bestDist;
            int tempResult = 0;
            Tuple<double, int> result;
            int aLen = a.Count, bLen = b.Count;

            //cases for one or more routes with only 1 city
            if (aLen < 2 && bLen < 2)
            {
                //find the best of the two possible routes
                //a to b then back
                bestDist = distanceGrid.GetDistance(a[0], b[0])
                            + distanceGrid.GetDistance(b[0], a[0]);
                result = new Tuple<double, int>(bestDist, 4);
                return result;
            }
            if (aLen < 2)
            {
                //find the loop distance if a[0] were inserted at b[j]
                bestDist = b.LoopDistance
                            + distanceGrid.GetDistance(b[j], a[0])
                            + distanceGrid.GetDistance(a[0], b[(j + 1) % bLen])
                            - distanceGrid.GetDistance(b[j], b[(j + 1) % bLen]);
                result = new Tuple<double, int>(bestDist, 5);
                return result;
            }
            if (bLen < 2)
            {
                //find the loop distance if b[0] were inserted at a[i]
                bestDist = a.LoopDistance
                            + distanceGrid.GetDistance(a[i], b[0])
                            + distanceGrid.GetDistance(b[0], a[(i + 1) % aLen])
                            - distanceGrid.GetDistance(a[i], a[(i + 1) % aLen]);
                result = new Tuple<double, int>(bestDist, 6);
                return result;
            }


            //case 0
            bestDist = tempDist = a.LoopDistance + b.LoopDistance
                                - distanceGrid.GetDistance(a[i], a[(i + 1) % aLen])//old
                                - distanceGrid.GetDistance(b[j], b[(j + 1) % bLen])//old
                                + distanceGrid.GetDistance(a[i], b[j]) //new
                                + distanceGrid.GetDistance(b[(j + 1) % bLen], a[(i + 1) % aLen]);//new
            tempResult = 0;

            //case 1
            tempDist = a.ReverseLoopDistance + b.ReverseLoopDistance
                                - distanceGrid.GetDistance(a[(i + 1) % aLen], a[i])//old
                                - distanceGrid.GetDistance(b[(j + 1) % bLen], b[j])//old
                                + distanceGrid.GetDistance(b[j], a[i])//new
                                + distanceGrid.GetDistance(a[(i + 1) % aLen], b[(j + 1) % bLen]);//new
            if (tempDist < bestDist)
            {
                bestDist = tempDist;
                tempResult = 1;
            }

            //case 2 (cross)
            tempDist = a.LoopDistance + b.ReverseLoopDistance
                                - distanceGrid.GetDistance(a[i], a[(i + 1) % aLen])//old
                                - distanceGrid.GetDistance(b[(j + 1) % bLen], b[j])//old
                                + distanceGrid.GetDistance(a[i], b[(j + 1) % bLen])//new
                                + distanceGrid.GetDistance(b[j], a[(i + 1) % aLen]);//new
            if (tempDist < bestDist)
            {
                bestDist = tempDist;
                tempResult = 2;
            }

            //case 3 (cross)
            tempDist = a.ReverseLoopDistance + b.LoopDistance
                                - distanceGrid.GetDistance(a[(i + 1) % aLen], a[i])//old
                                - distanceGrid.GetDistance(b[j], b[(j + 1) % bLen])//old
                                + distanceGrid.GetDistance(b[(j + 1) % bLen], a[i])//new
                                + distanceGrid.GetDistance(a[(i + 1) % aLen], b[j]);//new
            if (tempDist < bestDist)
            {
                bestDist = tempDist;
                tempResult = 3;
            }

            result = new Tuple<double, int>(bestDist, tempResult);
            return result;
        }

        /// <summary>
        /// Finds the four quadrants
        /// </summary>
        /// <param name="input">the list of cities</param>
        /// <param name="minX"></param>
        /// <param name="maxX"></param>
        /// <param name="minY"></param>
        /// <param name="maxY"></param>
        private void findMinMaxValues(List<City> input, out double minX, out double maxX,
                                        out double minY, out double maxY)
        {
            minX = maxX = input[0].X;
            minY = maxY = input[0].Y;

            for (int i = 1; i < input.Count; ++i)
            {
                double newX = input[i].X;
                double newY = input[i].Y;
                // set X
                if (minX > newX)
                    minX = newX;
                else if (maxX < newX)
                    maxX = newX;
                // set Y
                if (minY > newY)
                    minY = newY;
                else if (maxY < newY)
                    maxY = newY;
            }
        }
    }
}